package hot100;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/generate-parentheses
 */
public class GenerateParenthesis22 {
    int target;
    List<String> list;

    public List<String> generateParenthesis(int n) {
        list = new ArrayList<>();
        target = n;
        fun("",0,0);
        return list;
    }

    public void fun(String s,int count,int left){
        if (count==0 && left == target){
            list.add(s);
        }else if (count==0 && left<target){
            s+='(';
            fun(s,count+1,left+1);
        }else {
            if (left==target){
                s+=')';
                fun(s,count-1,left);
            }else {
                fun(s+'(',count+1,left+1);
                fun(s+')',count-1,left);
            }
        }
    }
}
